home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / snip9707.zip / DEQUE.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  19KB  |  875 lines

  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3.  
  4. /****************************************************************
  5.  *
  6.  *  File : DEQUE.c
  7.  *
  8.  *  Author: Peter Yard [1993.01.02] -- 02 Jan 1993
  9.  *
  10.  *  Disclaimer: This code is released to the public domain.
  11.  *
  12.  *  Description:
  13.  *      Generic double ended queue (Deque pronounced DEK) for handling
  14.  *      any data types, with sorting.
  15.  *
  16.  *      By use of various functions in this module the caller
  17.  *      can create stacks, queues, lists, doubly linked lists,
  18.  *      sorted lists, indexed lists.  All lists are dynamic.
  19.  *
  20.  *      It is the responsibility of the caller to malloc and free
  21.  *      memory for insertion into the queue. A pointer to the object
  22.  *      is used so that not only can any data be used but various kinds
  23.  *      of data can be pushed on the same queue if one so wished e.g.
  24.  *      various length string literals mixed with pointers to structures
  25.  *      or integers etc.
  26.  *
  27.  *  Enhancements:
  28.  *      A future improvement would be the option of multiple "cursors"
  29.  *      so that multiple locations could occur in the one queue to allow
  30.  *      placemarkers and additional flexibility.  Perhaps even use queue
  31.  *      itself to have a list of cursors.
  32.  *
  33.  * Usage:
  34.  *
  35.  *          /x init queue x/
  36.  *          queue  q;
  37.  *          Q_Init(&q);
  38.  *
  39.  *      To create a stack :
  40.  *
  41.  *          Q_PushHead(&q, &mydata1); /x push x/
  42.  *          Q_PushHead(&q, &mydata2);
  43.  *          .....
  44.  *          data_ptr = Q_PopHead(&q); /x pop x/
  45.  *          .....
  46.  *          data_ptr = Q_First(&q);   /x top of stack x/
  47.  *
  48.  *      To create a FIFO:
  49.  *
  50.  *          Q_PushHead(&q, &mydata1);
  51.  *          .....
  52.  *          data_ptr = Q_PopTail(&q);
  53.  *
  54.  *      To create a double list:
  55.  *
  56.  *          data_ptr = Q_First(&q);
  57.  *          ....
  58.  *          data_ptr = Q_Next(&q);
  59.  *          data_ptr = Q_Last(&q);
  60.  *          if (Q_Empty(&q)) ....
  61.  *          .....
  62.  *          data_ptr = Q_Previous(&q);
  63.  *
  64.  *      To create a sorted list:
  65.  *
  66.  *          Q_PushHead(&q, &mydata1); /x push x/
  67.  *          Q_PushHead(&q, &mydata2);
  68.  *          .....
  69.  *          if (!Q_Sort(&q, MyFunction))
  70.  *              .. error ..
  71.  *
  72.  *          /x fill in key field of mydata1.
  73.  *           * NB: Q_Find does linear search
  74.  *           x/
  75.  *
  76.  *          if (Q_Find(&q, &mydata1, MyFunction))
  77.  *          {
  78.  *              /x found it, queue cursor now at correct record x/
  79.  *              /x can retrieve with x/
  80.  *              data_ptr = Q_Get(&q);
  81.  *
  82.  *              /x alter data , write back with x/
  83.  *              Q_Put(&q, data_ptr);
  84.  *          }
  85.  *
  86.  *          /x Search with binary search x/
  87.  *          if (Q_Seek(&q, &mydata, MyFunction))
  88.  *              /x etc x/
  89.  *
  90.  *
  91.  ****************************************************************/
  92.  
  93.  
  94. #include <stdlib.h>
  95.  
  96. #include "deque.h"
  97.  
  98.  
  99. static void QuickSort(void *list[], int low, int high,
  100.                       int (*Comp)(const void *, const void *));
  101. static int  Q_BSearch(queue *q, void *key,
  102.                       int (*Comp)(const void *, const void *));
  103.  
  104. /* The index: a pointer to pointers */
  105.  
  106. static  void        **index;
  107. static  datanode    **posn_index;
  108.  
  109.  
  110. /***
  111.  *
  112.  ** function    : Q_Init
  113.  *
  114.  ** purpose     : Initialise queue object and pointers.
  115.  *
  116.  ** parameters  : 'queue' pointer.
  117.  *
  118.  ** returns     : True_ if init successful else False_
  119.  *
  120.  ** comments    :
  121.  ***/
  122.  
  123. int Q_Init(queue  *q)
  124. {
  125.       q->head = q->tail = NULL;
  126.       q->cursor = q->head;
  127.       q->size = 0;
  128.       q->sorted = False_;
  129.  
  130.       return True_;
  131. }
  132.  
  133. /***
  134.  *
  135.  ** function    : Q_Start
  136.  *
  137.  ** purpose     : tests if cursor is at head of queue
  138.  *
  139.  ** parameters  : 'queue' pointer.
  140.  *
  141.  ** returns     : boolean - True_ is at head else False_
  142.  *
  143.  ** comments    :
  144.  *
  145.  ***/
  146.  
  147. int Q_Start(queue *q)
  148. {
  149.       return (q->cursor == q->head);
  150. }
  151.  
  152.  
  153. /***
  154.  *
  155.  ** function    : Q_End
  156.  *
  157.  ** purpose     : boolean test if cursor at tail of queue
  158.  *
  159.  ** parameters  : 'queue' pointer to test.
  160.  *
  161.  ** returns     : True_ or False_
  162.  *
  163.  ** comments    :
  164.  *
  165.  ***/
  166.  
  167. int Q_End(queue *q)
  168. {
  169.       return (q->cursor == q->tail);
  170. }
  171.  
  172.  
  173. /***
  174.  *
  175.  ** function    : Q_Empty
  176.  *
  177.  ** purpose     : test if queue has nothing in it.
  178.  *
  179.  ** parameters  : 'queue' pointer
  180.  *
  181.  ** returns     : True_ if empty queue, else False_
  182.  *
  183.  ** comments    :
  184.  *
  185.  ***/
  186.  
  187. int Q_Empty(queue *q)
  188. {
  189.       return (q->size == 0);
  190. }
  191.  
  192. /***
  193.  *
  194.  ** function    : Q_Size
  195.  *
  196.  ** purpose     : return the number of elements in the queue
  197.  *
  198.  ** parameters  : queue pointer
  199.  *
  200.  ** returns     : number of elements
  201.  *
  202.  ** comments    :
  203.  *
  204.  ***/
  205.  
  206. int Q_Size(queue *q)
  207. {
  208.       return q->size;
  209. }
  210.  
  211.  
  212. /***
  213.  *
  214.  ** function    : Q_First
  215.  *
  216.  ** purpose     : position queue cursor to first element (head) of queue.
  217.  *
  218.  ** parameters  : 'queue' pointer
  219.  *
  220.  ** returns     : pointer to data at head. If queue is empty returns NULL
  221.  *
  222.  ** comments    :
  223.  *
  224.  ***/
  225.  
  226. void *Q_First(queue *q)
  227. {
  228.       if (Q_Empty(q))
  229.             return NULL;
  230.  
  231.       q->cursor = q->head;
  232.  
  233.       return  q->cursor->data;
  234. }
  235.  
  236.  
  237. /***
  238.  *
  239.  ** function    : Q_Last
  240.  *
  241.  ** purpose     : locate cursor at tail of queue.
  242.  *
  243.  ** parameters  : 'queue' pointer
  244.  *
  245.  ** returns     : pointer to data at tail , if queue empty returns NULL
  246.  *
  247.  ** comments    :
  248.  *
  249.  ***/
  250.  
  251. void *Q_Last(queue *q)
  252. {
  253.       if (Q_Empty(q))
  254.             return NULL;
  255.  
  256.       q->cursor = q->tail;
  257.  
  258.       return  q->cursor->data;
  259. }
  260.  
  261.  
  262. /***
  263.  *
  264.  ** function    : Q_PushHead
  265.  *
  266.  ** purpose     : put a data pointer at the head of the queue
  267.  *
  268.  ** parameters  : 'queue' pointer, void pointer to the data.
  269.  *
  270.  ** returns     : True_ if success else False_ if unable to push data.
  271.  *
  272.  ** comments    :
  273.  *
  274.  ***/
  275.  
  276. int Q_PushHead(queue *q, void *d)
  277. {
  278.       node    *n;
  279.       datanode *p;
  280.  
  281.       q->head->prev = malloc(sizeof(datanode));
  282.       if (q->head->prev == NULL)
  283.             return False_;
  284.  
  285.       n = q->head;
  286.  
  287.       p = q->head->prev;
  288.       q->head = (node*)p;
  289.       q->head->prev = NULL;
  290.  
  291.       if (q->size == 0)
  292.       {
  293.             q->head->next = NULL;
  294.             q->tail = q->head;
  295.       }
  296.       else  q->head->next = (datanode*)n;
  297.  
  298.       q->head->data = d;
  299.       q->size++;
  300.  
  301.       q->cursor = q->head;
  302.  
  303.       q->sorted = False_;
  304.  
  305.       return True_;
  306. }
  307.  
  308.  
  309.  
  310. /***
  311.  *
  312.  ** function    : Q_PushTail
  313.  *
  314.  ** purpose     : put a data element pointer at the tail of the queue
  315.  *
  316.  ** parameters  : queue pointer, pointer to the data
  317.  *
  318.  ** returns     : True_ if data pushed, False_ if data not inserted.
  319.  *
  320.  ** comments    :
  321.  *
  322.  ***/
  323.  
  324. int Q_PushTail(queue *q, void *d)
  325. {
  326.       node        *p;
  327.       datanode    *n;
  328.  
  329.       q->tail->next = malloc(sizeof(datanode));
  330.       if (q->tail->next == NULL)
  331.             return False_;
  332.  
  333.       p = q->tail;
  334.       n = q->tail->next;
  335.       q->tail = (node *)n;
  336.  
  337.       if (q->size == 0)
  338.       {
  339.             q->tail->prev = NULL;
  340.             q->head = q->tail;
  341.       }
  342.       else  q->tail->prev = (datanode *)p;
  343.  
  344.       q->tail->next = NULL;
  345.  
  346.       q->tail->data =  d;
  347.       q->cursor = q->tail;
  348.       q->size++;
  349.  
  350.       q->sorted = False_;
  351.  
  352.       return True_;
  353. }
  354.  
  355.  
  356.  
  357. /***
  358.  *
  359.  ** function    : Q_PopHead
  360.  *
  361.  ** purpose     : remove and return the top element at the head of the
  362.  *                queue.
  363.  *
  364.  ** parameters  : queue pointer
  365.  *
  366.  ** returns     : pointer to data element or NULL if queue is empty.
  367.  *
  368.  ** comments    :
  369.  *
  370.  ***/
  371.  
  372. void *Q_PopHead(queue *q)
  373. {
  374.       datanode    *n;
  375.       void        *d;
  376.  
  377.       if (Q_Empty(q))
  378.             return NULL;
  379.  
  380.       d = q->head->data;
  381.       n = q->head->next;
  382.       free(q->head);
  383.  
  384.       q->size--;
  385.  
  386.       if (q->size == 0)
  387.             q->head = q->tail = q->cursor = NULL;
  388.       else
  389.       {
  390.             q->head = (node *)n;
  391.             q->head->prev = NULL;
  392.             q->cursor = q->head;
  393.       }
  394.  
  395.       q->sorted = False_;
  396.  
  397.       return d;
  398. }
  399.  
  400.  
  401. /***
  402.  *
  403.  ** function    : Q_PopTail
  404.  *
  405.  ** purpose     : remove element from tail of queue and return data.
  406.  *
  407.  ** parameters  : queue pointer
  408.  *
  409.  ** returns     : pointer to data element that was at tail. NULL if queue
  410.  *                empty.
  411.  *
  412.  ** comments    :
  413.  *
  414.  ***/
  415.  
  416. void *Q_PopTail(queue *q)
  417. {
  418.       datanode    *p;
  419.       void        *d;
  420.  
  421.       if (Q_Empty(q))
  422.             return NULL;
  423.  
  424.       d = q->tail->data;
  425.       p = q->tail->prev;
  426.       free(q->tail);
  427.       q->size--;
  428.  
  429.       if (q->size == 0)
  430.             q->head = q->tail = q->cursor = NULL;
  431.       else
  432.       {
  433.             q->tail = (node *)p;
  434.             q->tail->next = NULL;
  435.             q->cursor = q->tail;
  436.       }
  437.  
  438.       q->sorted = False_;
  439.  
  440.       return d;
  441. }
  442.  
  443.  
  444.  
  445. /***
  446.  *
  447.  ** function    : Q_Next
  448.  *
  449.  ** purpose     : Move to the next element in the queue without popping
  450.  *
  451.  ** parameters  : queue pointer.
  452.  *
  453.  ** returns     : pointer to data element of new element or NULL if end
  454.  *                of the queue.
  455.  *
  456.  ** comments    : This uses the cursor for the current position. Q_Next
  457.  *                only moves in the direction from the head of the queue
  458.  *                to the tail.
  459.  ***/
  460.  
  461. void *Q_Next(queue *q)
  462. {
  463.       if (q->cursor->next == NULL)
  464.             return NULL;
  465.  
  466.       q->cursor = (node *)q->cursor->next;
  467.  
  468.       return  q->cursor->data ;
  469. }
  470.  
  471.  
  472.  
  473. /***
  474.  *
  475.  ** function    : Q_Previous
  476.  *
  477.  ** purpose     : Opposite of Q_Next. Move to next element closer to the
  478.  *                head of the queue.
  479.  *
  480.  ** parameters  : pointer to queue
  481.  *
  482.  ** returns     : pointer to data of new element else NULL if queue empty
  483.  *
  484.  ** comments    : Makes cursor move towards the head of the queue.
  485.  *
  486.  ***/
  487.  
  488. void *Q_Previous(queue *q)
  489. {
  490.       if (q->cursor->prev == NULL)
  491.             return NULL;
  492.  
  493.       q->cursor = (node *)q->cursor->prev;
  494.  
  495.       return q->cursor->data;
  496. }
  497.  
  498.  
  499.  
  500. /***
  501.  *
  502.  ** function    : Q_DelCur
  503.  *
  504.  ** purpose     : Delete the current queue element as pointed to by
  505.  *                the cursor.
  506.  *
  507.  ** parameters  : queue pointer
  508.  *
  509.  ** returns     : pointer to data element.
  510.  *
  511.  ** comments    : WARNING! It is the responsibility of the caller to
  512.  *                free any memory. Queue cannot distinguish between
  513.  *                pointers to literals and malloced memory.
  514.  *
  515.  ***/
  516.  
  517. void *Q_DelCur(queue *q)
  518. {
  519.       void        *d;
  520.       datanode    *n, *p;
  521.  
  522.       if (q->cursor == NULL)
  523.             return NULL;
  524.  
  525.       if (q->cursor == q->head)
  526.             return Q_PopHead(q);
  527.  
  528.       if (q->cursor == q->tail)
  529.             return Q_PopTail(q);
  530.  
  531.       n = q->cursor->next;
  532.       p = q->cursor->prev;
  533.       d = q->cursor->data;
  534.  
  535.       free(q->cursor);
  536.       if (p != NULL)
  537.             q->cursor = p;
  538.       else  q->cursor = n;
  539.       q->size--;
  540.  
  541.       q->sorted = False_;
  542.  
  543.       return d;
  544. }
  545.  
  546.  
  547.  
  548. /***
  549.  *
  550.  ** function    : Q_Get
  551.  *
  552.  ** purpose     : get the pointer to the data at the cursor location
  553.  *
  554.  ** parameters  : queue pointer
  555.  *
  556.  ** returns     : data element pointer
  557.  *
  558.  ** comments    :
  559.  *
  560.  ***/
  561.  
  562. void *Q_Get(queue *q)
  563. {
  564.       if (q->cursor == NULL)
  565.             return NULL;
  566.       return q->cursor->data;
  567. }
  568.  
  569.  
  570.  
  571. /***
  572.  *
  573.  ** function    : Q_Put
  574.  *
  575.  ** purpose     : replace pointer to data with new pointer to data.
  576.  *
  577.  ** parameters  : queue pointer, data pointer
  578.  *
  579.  ** returns     : boolean- True_ if successful, False_ if cursor at NULL
  580.  *
  581.  ** comments    :
  582.  *
  583.  ***/
  584.  
  585. int Q_Put(queue *q, void *data)
  586. {
  587.       if (q->cursor == NULL)
  588.             return False_;
  589.  
  590.       q->cursor->data = data;
  591.       return True_;
  592. }
  593.  
  594.  
  595. /***
  596.  *
  597.  ** function    : Q_Find
  598.  *
  599.  ** purpose     : Linear search of queue for match with key in *data
  600.  *
  601.  ** parameters  : queue pointer q, data pointer with data containing key
  602.  *                comparison function here called Comp.
  603.  *
  604.  ** returns     : True_ if found , False_ if not in queue.
  605.  *
  606.  ** comments    : Useful for small queues that are constantly changing
  607.  *                and would otherwise need constant sorting with the
  608.  *                Q_Seek function.
  609.  *                For description of Comp see Q_Sort.
  610.  *                Queue cursor left on position found item else at end.
  611.  *
  612.  ***/
  613.  
  614. int Q_Find(queue *q, void *data,
  615.                int (*Comp)(const void *, const void *))
  616. {
  617.       void *d;
  618.       d = Q_First(q);
  619.       do
  620.       {
  621.             if (Comp(d, data) == 0)
  622.                   return True_;
  623.             d = Q_Next(q);
  624.       } while (!Q_End(q));
  625.  
  626.       if (Comp(d, data) == 0)
  627.             return True_;
  628.  
  629.       return False_;
  630. }
  631.  
  632. /*========  Sorted Queue and Index functions   ========= */
  633.  
  634.  
  635. static void QuickSort(void *list[], int low, int high,
  636.                       int (*Comp)(const void *, const void *))
  637. {
  638.       int     flag = 1, i, j;
  639.       void    *key, *temp;
  640.  
  641.       if (low < high)
  642.       {
  643.             i = low;
  644.             j = high + 1;
  645.  
  646.             key = list[ low ];
  647.  
  648.             while (flag)
  649.             {
  650.                   i++;
  651.                   while (Comp(list[i], key) < 0)
  652.                         i++;
  653.  
  654.                   j--;
  655.                   while (Comp(list[j], key) > 0)
  656.                         j--;
  657.  
  658.                   if (i < j)
  659.                   {
  660.                         temp = list[i];
  661.                         list[i] = list[j];
  662.                         list[j] = temp;
  663.                   }
  664.                   else  flag = 0;
  665.             }
  666.  
  667.             temp = list[low];
  668.             list[low] = list[j];
  669.             list[j] = temp;
  670.  
  671.             QuickSort(list, low, j-1, Comp);
  672.             QuickSort(list, j+1, high, Comp);
  673.       }
  674. }
  675.  
  676.  
  677. /***
  678.  *
  679.  ** function    : Q_Sort
  680.  *
  681.  ** purpose     : sort the queue and allow index style access.
  682.  *
  683.  ** parameters  : queue pointer, comparison function compatible with
  684.  *                with 'qsort'.
  685.  *
  686.  ** returns     : True_ if sort succeeded. False_ if error occurred.
  687.  *
  688.  ** comments    : Comp function supplied by caller must return
  689.  *                  -1 if data1  < data2
  690.  *                   0 if data1 == data2
  691.  *                  +1 if data1  > data2
  692.  *
  693.  *                    for Comp(data1, data2)
  694.  *
  695.  *                If queue is already sorted it frees the memory of the
  696.  *                old index and starts again.
  697.  *
  698.  ***/
  699.  
  700. int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
  701. {
  702.       int         i;
  703.       void        *d;
  704.       datanode    *dn;
  705.  
  706.       /* if already sorted free memory for tag array */
  707.  
  708.       if (q->sorted)
  709.       {
  710.             free(index);
  711.             free(posn_index);
  712.             q->sorted = False_;
  713.       }
  714.  
  715.       /* Now allocate memory of array, array of pointers */
  716.  
  717.       index = malloc(q->size * sizeof(q->cursor->data));
  718.       if (index == NULL)
  719.             return False_;
  720.  
  721.       posn_index = malloc(q->size * sizeof(q->cursor));
  722.       if (posn_index == NULL)
  723.       {
  724.             free(index);
  725.             return False_;
  726.       }
  727.  
  728.       /* Walk queue putting pointers into array */
  729.  
  730.       d = Q_First(q);
  731.       for (i=0; i < q->size; i++)
  732.       {
  733.             index[i] = d;
  734.             posn_index[i] = q->cursor;
  735.             d = Q_Next(q);
  736.       }
  737.  
  738.       /* Now sort the index */
  739.  
  740.       QuickSort(index, 0, q->size - 1, Comp);
  741.  
  742.       /* Rearrange the actual queue into correct order */
  743.  
  744.       dn = q->head;
  745.       i = 0;
  746.       while (dn != NULL)
  747.       {
  748.             dn->data = index[i++];
  749.             dn = dn->next;
  750.       }
  751.  
  752.       /* Re-position to original element */
  753.  
  754.       if (d != NULL)
  755.             Q_Find(q, d, Comp);
  756.       else  Q_First(q);
  757.  
  758.       q->sorted = True_;
  759.  
  760.       return True_;
  761. }
  762.  
  763.  
  764. /***
  765.  *
  766.  ** function    : Q_BSearch
  767.  *
  768.  ** purpose     : binary search of queue index for node containing key
  769.  *
  770.  ** parameters  : queue pointer 'q', data pointer of key 'key',
  771.  *                  Comp comparison function.
  772.  *
  773.  ** returns     : integer index into array of node pointers,
  774.  *                or -1 if not found.
  775.  *
  776.  ** comments    : see Q_Sort for description of 'Comp' function.
  777.  *
  778.  ***/
  779.  
  780. static int Q_BSearch( queue *q, void *key,
  781.                       int (*Comp)(const void *, const void*))
  782. {
  783.       int low, mid, hi, val;
  784.  
  785.       low = 0;
  786.       hi = q->size - 1;
  787.  
  788.       while (low <= hi)
  789.       {
  790.             mid = (low + hi) / 2;
  791.             val = Comp(key, index[ mid ]);
  792.  
  793.             if (val < 0)
  794.                   hi = mid - 1;
  795.  
  796.             else if (val > 0)
  797.                   low = mid + 1;
  798.  
  799.             else /* Success */
  800.                   return mid;
  801.       }
  802.  
  803.       /* Not Found */
  804.  
  805.       return -1;
  806. }
  807.  
  808.  
  809. /***
  810.  *
  811.  ** function    : Q_Seek
  812.  *
  813.  ** purpose     : use index to locate data according to key in 'data'
  814.  *
  815.  ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
  816.  *                function.
  817.  *
  818.  ** returns     : pointer to data or NULL if could not find it or could
  819.  *                not sort queue.
  820.  *
  821.  ** comments    : see Q_Sort for description of 'Comp' function.
  822.  *
  823.  ***/
  824.  
  825. void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
  826. {
  827.       int idx;
  828.  
  829.       if (!q->sorted)
  830.       {
  831.             if (!Q_Sort(q, Comp))
  832.                   return NULL;
  833.       }
  834.  
  835.       idx = Q_BSearch(q, data, Comp);
  836.  
  837.       if (idx < 0)
  838.             return NULL;
  839.  
  840.       q->cursor = posn_index[idx];
  841.  
  842.       return index[idx];
  843. }
  844.  
  845.  
  846.  
  847. /***
  848.  *
  849.  ** function    : Q_Insert
  850.  *
  851.  ** purpose     : Insert an element into an indexed queue
  852.  *
  853.  ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
  854.  *                function.
  855.  *
  856.  ** returns     : pointer to data or NULL if could not find it or could
  857.  *                not sort queue.
  858.  *
  859.  ** comments    : see Q_Sort for description of 'Comp' function.
  860.  *                WARNING! This code can be very slow since each new
  861.  *                element means a new Q_Sort.  Should only be used for
  862.  *                the insertion of the odd element ,not the piecemeal
  863.  *                building of an entire queue.
  864.  ***/
  865.  
  866. int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
  867. {
  868.       Q_PushHead(q, data);
  869.  
  870.       if (!Q_Sort(q, Comp))
  871.             return False_;
  872.  
  873.       return True_;
  874. }
  875.